package com.lw.leetcode.back.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 2305. 公平分发饼干
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/28 11:38
 */
public class DistributeCookies {


    public static void main(String[] args) {
        DistributeCookies test = new DistributeCookies();

        // 31
//        int[] cookies = {8, 15, 10, 20, 8};
//        int k = 2;

        // 7
//        int[] cookies = {6, 1, 3, 2, 2, 4, 1, 2};
//        int k = 3;

        // 6365
        int[] cookies = {6365, 4671, 5643, 2433, 253, 2474, 5421, 5752};
        int k = 7;

        int i = test.distributeCookies(cookies, k);
        System.out.println(i);
    }


    private int[] cookies;
    private int k;
    private int limit;
    private int max = Integer.MAX_VALUE;

    public int distributeCookies(int[] cookies, int k) {
        this.cookies = cookies;
        this.k = k;
        int length = cookies.length;
        int sum = 0;
        for (int cookie : cookies) {
            sum += cookie;
        }
        this.limit = (sum + k - 1) / k;
        Arrays.sort(cookies);
        int[] arr = new int[k];
        arr[0] = cookies[length - 1];
        find(length - 2, arr);
        return max;
    }

    private void find(int index, int[] arr) {
        if (index < 0) {
            int m = 0;
            for (int i : arr) {
                m = Math.max(m, i);
            }
            max = Math.min(max, m);
            return;
        }
        int v = cookies[index];
        for (int i = 0; i < k; i++) {
            if (arr[i] > limit || (getZero(arr) == index + 1 && arr[i] != 0)) {
                continue;
            }
            arr[i] += v;
            find(index - 1, arr);
            arr[i] -= v;
        }
    }

    private int getZero(int[] arr) {
        int c = 0;
        for (int i : arr) {
            if (i == 0) {
                c++;
            }
        }
        return c;
    }

}
